#pragma once
#include <string>
#include <algorithm>

template<typename T>
class List
{
private:
  struct Node
  {
    Node();
    Node(const T& i_node);
    T key;
    Node *prev;
    Node *next;
  } *mp_head;
  Node* lastNode()
  {
    for (auto iter = mp_head; iter != nullptr; iter = iter->next)
    {
      if (iter->next == nullptr)
      {
        return iter;
      }
    }
    return nullptr;
  };
  Node* pop_front_Node()
  {
    if (empty())
      return nullptr;
    Node* front_node = mp_head;
    if (mp_head->next == nullptr)
    {
      mp_head = nullptr;
      return front_node;
    }
    mp_head = mp_head->next;
    mp_head->prev = nullptr;
    front_node->next = nullptr;
    front_node->prev = nullptr;
    return front_node;
  };
  void makeHead(Node *ip_newhead);
  bool eraseNode(Node* ip_node_to_delete);
  void insert_Node(Node* ip_where, Node* ip_what);
public:
  List();
  ~List();
  bool find(const T &i_key); // TODO
  bool push_back(const T &i_key); //+
  bool push_front(const T &i_key); //+
  bool pop_back(); //+
  bool pop_front(); //+
  bool erase(const T &i_key); //+
  int clear(); //+
  void show_list(); //+
  void merge(List& i_list); //+
  void splice(int i_pos, List& i_list); // TODO
  bool is_sort() const; //+
  void sort(); // +
  void swap(Node* first, Node* second); //+ (write my own swap) 
  int size() const; //+
  bool empty() const; //+
  T& first();
  const T& first() const;
  T& back();
  T& element(int i_pos);
};

template <typename T>
List<T>::Node::Node(const T& i_node) : key(i_node), prev(nullptr), next(nullptr)
{
}

template <typename T>
List<T>::List() : mp_head(nullptr)
{
}

template<typename T>
List<T>::~List()
{
  clear();
}


template<typename T>
T& List<T>::first()
{
  return mp_head->key;
}

template<typename T>
T& List<T>::element(int i_pos)
{
  if (i_pos > size() - 1)
    throw "Invalid";
  auto iter = mp_head;
  for (; iter != nullptr && i_pos != 0; iter = iter->next, --i_pos)
  {
    int i = i_pos;
  }
  if (iter != nullptr)
    return iter->key;
}

template<typename T>
const T& List<T>::first() const
{
  return mp_head->key;
}


template<typename T>
T& List<T>::back()
{
  auto last = lastNode();
  return last->key;
}

template<typename T>
bool List<T>::erase(const T &i_key)
{
  if (empty())
    return false;

  for (auto iter = mp_head; iter != nullptr; iter = iter->next)
  {
    if (iter->key == i_key)
    {
      eraseNode(iter);
      break;
    }
  }
  return true;
}


template<typename T>
bool List<T>::eraseNode(Node* ip_node_to_delete)
{
  if (empty())
    return false;
  Node *del = ip_node_to_delete;
  Node *prev = nullptr;
  if (del == mp_head)
  {
    mp_head = del->next;
  }
  else
  {
    prev = mp_head->next;
    while (prev->next != del && prev->next != NULL)
    {
      prev = prev->next;
    }
    del->prev->next = del->next;
  }
  del = del->next;
  //delete del; ????
  return true;
}


template<typename T>
int List<T>::size() const
{
  int count = 0;
  for (auto iter = mp_head; iter != nullptr; iter = iter->next)
  {
    count++;
  }
  return count;
}


template<typename T>
bool List<T>::empty() const
{
  return mp_head == nullptr;
}

template<typename T>
void List<T>::insert_Node(Node* ip_where, Node* ip_what)
{
  if (empty())
    return;
  if (ip_what == nullptr)
    return;
  Node* next_insert_node = ip_where->next;
  ip_where->next = ip_what;
  ip_what->next = next_insert_node;

  ip_what->prev = ip_where;
  if (next_insert_node != nullptr)
    next_insert_node->prev = ip_what;
}


template<typename T>
void List<T>::merge(List& i_list)
{
  if (empty() && !i_list.empty())
    makeHead(i_list.pop_front_Node());
  if (i_list.empty() && !empty())
    return;
  //makeHead(mp_head); //???
  if (!i_list.is_sort())
  {
    i_list.sort();
  }
  if (!is_sort())
  {
    sort();
  }


  if (first() > i_list.first())
  {
    makeHead(i_list.pop_front_Node());
  }

  for (auto iter = mp_head; iter != nullptr && !i_list.empty(); iter = iter->next)
  {
    if (iter->key <= i_list.first() && iter->next != nullptr && iter->next->key > i_list.first())
    {
      insert_Node(iter, i_list.pop_front_Node());
    }
    else if (iter->next == nullptr)
      insert_Node(lastNode(), i_list.pop_front_Node());
  }

  if (!i_list.empty())
    splice(size() - 1, i_list);
}


template<typename T>
void List<T>::splice(int i_pos, List& i_list)
{
  if (empty() || i_list.empty())
    return;

  if (i_pos > size())
    return;

  auto list_to_insert = i_list.mp_head;
  i_list.mp_head = nullptr;
  if (i_pos == size())
  {
    lastNode()->next = list_to_insert;
    list_to_insert->prev = lastNode();
  }
  else
  {
    Node* iter = nullptr;
    auto iter_next = mp_head;

    for (int i = 0; i < i_pos && iter_next != nullptr; ++i, iter = iter_next, iter_next = iter->next);

    auto temp = iter_next;
    if (iter)
      iter->next = list_to_insert;
    else
      mp_head = list_to_insert;
    list_to_insert->prev = iter;
    lastNode()->next = temp;
    temp->prev = lastNode();
  }
}


template<typename T>
bool List<T>::is_sort() const
{
  if (empty())
    return false;
  for (auto iter = mp_head; iter->next != nullptr; iter = iter->next)
  {
    if (iter->key > iter->next->key)
    {
      return false;
    }
  }
  return true;
}

template<typename T>
int List<T>::clear()
{
  if (empty())
    return 0;
  int count;
  for (count = 0; !empty(); ++count)
  {
    Node* to_delete = mp_head;
    mp_head = mp_head->next;
    delete to_delete;
  }
  delete mp_head;
  return count;
}


template<typename T>
void List<T>::sort()
{
  if (empty())
    cout << "The list is empty\n";

  for (auto i = 1; i < size(); i++)
  {
    for (auto iter = mp_head; iter != nullptr; iter = iter->next)
    {
      while (iter->prev && iter->key < iter->prev->key)
        swap(iter, iter->prev);
    }
  }
}


template<typename T>
void List<T>::swap(Node* ip_left, Node* ip_right)
{
  if (!ip_left || !ip_right)
    return;

  std::swap(ip_left->key, ip_right->key);
  return;
}



template<typename T>
void List<T>::makeHead(Node* ip_newhead)
{
  if (!empty())
  {
    ip_newhead->next = mp_head;
    mp_head->prev = ip_newhead;
    mp_head = ip_newhead;
  }
  else
    mp_head = ip_newhead;
}

template<typename T>
bool List<T>::push_back(const T &i_key)
{
  Node *temp = new Node(i_key);

  if (empty())
  {
    makeHead(temp);
  }
  else
  {
    Node *last = lastNode();
    last->next = temp;
    temp->prev = last;
  }
  return true;
}

template<typename T>
bool List<T>::push_front(const T &i_key)
{
  Node *temp = new Node(i_key);

  if (mp_head == nullptr)
  {
    mp_head = temp;
  }
  else
  {
    temp->next = mp_head;
    mp_head = temp;
  }
  return true;
}

template<typename T>
bool List<T>::pop_back()
{
  if (empty())
    return false;
  Node* last = lastNode();
  last->prev->next = nullptr;
  delete last;
  return true;
}


template<typename T>
bool List<T>::pop_front()
{
  if (empty())
    return false;
  Node* first = mp_head;
  mp_head = mp_head->next;
  mp_head->prev = nullptr;
  delete first;
  return true;
}

template<typename T>
bool List<T>::find(const T& i_key)
{
  for (auto iter = mp_head; iter != nullptr; iter = iter->next)
  {
    if (iter->key == i_key)
    {
      cout << "Elemnet " << iter->key << " was found!" << endl;
      return true;
    }
  }
  return false;
}

template<typename T>
void List<T>::show_list()
{
  for (auto iter = mp_head; iter != nullptr; iter = iter->next)
  {
    cout << iter->key << " ";
  }
  cout << "\n";
}
